LeetCode：图论（BSF&DFS，最短路径，染色问题，拓扑结构，并查集） |
您所在的位置：网站首页 › 图论 染色问题 › LeetCode：图论（BSF&DFS，最短路径，染色问题，拓扑结构，并查集） |
LeetCode：图论（BSF&DFS，最短路径，染色问题，拓扑结构，并查集）
|
1，广度优先遍历
面试题13，机器人的运动范围
题目：地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ class Solution { int[] dx = {1, 0, 0, -1}; int[] dy = {0, 1, -1, 0}; public int movingCount(int m, int n, int k) { ArrayList arrayList = new ArrayList(); Queue queue = new LinkedList(); queue.add(new int[]{0, 0}); arrayList.add(0 + "," + 0); while (!queue.isEmpty()) { int[] middle = queue.poll(); for (int i = 0; i < 4; i++) { int newX = middle[0] + dx[i]; int newY = middle[1] + dy[i]; int[] newPoint = new int[]{newX, newY}; if (!arrayList.contains(newX + "," + newY)) { int t = subtractProductAndSum(newX) + subtractProductAndSum(newY); if (newX >= 0 && newX < m && newY >= 0 && newY < n && t {-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int[][] heights; int m, n; public List pacificAtlantic(int[][] heights) { this.heights = heights; this.m = heights.length; this.n = heights[0].length; boolean[][] pacific = new boolean[m][n]; boolean[][] atlantic = new boolean[m][n]; for (int i = 0; i < m; i++) { bfs(i, 0, pacific); } for (int j = 1; j < n; j++) { bfs(0, j, pacific); } for (int i = 0; i < m; i++) { bfs(i, n - 1, atlantic); } for (int j = 0; j < n - 1; j++) { bfs(m - 1, j, atlantic); } List result = new ArrayList(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (pacific[i][j] && atlantic[i][j]) { List cell = new ArrayList(); cell.add(i); cell.add(j); result.add(cell); } } } return result; } public void bfs(int row, int col, boolean[][] ocean) { if (ocean[row][col]) { return; } ocean[row][col] = true; Queue queue = new ArrayDeque(); queue.offer(new int[]{row, col}); while (!queue.isEmpty()) { int[] cell = queue.poll(); for (int[] dir : dirs) { int newRow = cell[0] + dir[0], newCol = cell[1] + dir[1]; if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[cell[0]][cell[1]] && !ocean[newRow][newCol]) { ocean[newRow][newCol] = true; queue.offer(new int[]{newRow, newCol}); } } } } } 542，01矩阵题目：给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1 。
题目：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。 class Solution { int[] dx = {1, 0, 0, -1}; int[] dy = {0, 1, -1, 0}; public int findCircleNum(int[][] grid) { Queue queue = new LinkedList(); int heigh = grid.length; int width = grid[0].length; int max = 0; for (int i = 0; i < heigh; i++) { queue.clear(); //没有被访问过 if (grid[i][i] == 1) { //System.out.println(i); max++; queue.add(new int[]{i, i}); grid[i][i] = 0; for (int j = i; j < width; j++) { if (grid[i][j] == 1) { queue.add(new int[]{j, j}); grid[i][j] = 0; grid[j][j] = 0; grid[j][i] = 0; } } while (!queue.isEmpty()) { int middle[] = queue.poll(); for (int j = 0; j < width; j++) { if (grid[middle[0]][j] == 1) { queue.add(new int[]{j, j}); grid[middle[0]][j] = 0; grid[j][j] = 0; grid[j][middle[0]] = 0; } } } } } return max; } } 684，多余的边（冗余连接）题目：树可以看成是一个连通且 无环 的 无向 图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。 class Solution { int[] parent; int find(int idx) { if (parent[idx] != idx) parent[idx] = find(parent[idx]); return parent[idx]; } void union(int x, int y) { parent[find(x)] = find(y); } public int[] findRedundantConnection(int[][] edges) { int n = edges.length; parent = new int[n + 1]; for (int i = 0; i < n; i++) { parent[i] = i; } for (int[] e : edges) { int x = e[0], y = e[1]; if (find(x) != find(y)) union(x, y); else return e; } return new int[0]; } } 695，岛屿最大面积题目：给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。 思路：力扣 class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } int n = routes.length; boolean[][] edge = new boolean[n][n]; Map rec = new HashMap(); for (int i = 0; i < n; i++) { for (int site : routes[i]) { List list = rec.getOrDefault(site, new ArrayList()); for (int j : list) { edge[i][j] = edge[j][i] = true; } list.add(i); rec.put(site, list); } } int[] dis = new int[n]; Arrays.fill(dis, -1); Queue que = new LinkedList(); for (int bus : rec.getOrDefault(source, new ArrayList())) { dis[bus] = 1; que.offer(bus); } while (!que.isEmpty()) { int x = que.poll(); for (int y = 0; y < n; y++) { if (edge[x][y] && dis[y] == -1) { dis[y] = dis[x] + 1; que.offer(y); } } } int ret = Integer.MAX_VALUE; for (int bus : rec.getOrDefault(target, new ArrayList())) { if (dis[bus] != -1) { ret = Math.min(ret, dis[bus]); } } return ret == Integer.MAX_VALUE ? -1 : ret; } } 994，腐烂的橘子题目：在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： 值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
题目：有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。 class Solution { public boolean canVisitAllRooms(List rooms) { Queue queue = new LinkedList(); boolean[] visited = new boolean[rooms.size()]; queue.add(rooms.get(0)); while (!queue.isEmpty()) { ArrayList temp = (ArrayList) queue.poll(); for (int i = 0; i < temp.size(); i++) { if (!visited[temp.get(i)]) { queue.add(rooms.get(temp.get(i))); visited[temp.get(i)]=true; } } } for (int i = 1; i < visited.length; i++) { if (visited[i] == false) { return false; } } return true; } } 997，找到小镇的法官题目：小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。如果小镇法官真的存在，那么： 小镇法官不会信任任何人。每个人（除了小镇法官）都信任这位小镇法官。只有一个人同时满足属性 1 和属性 2 。给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。 如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。 思路：在法官存在的情况下，法官不相信任何人，每个人（除了法官外）都信任法官，且只有一名法官。因此法官这个节点的入度是 n-1, 出度是 0。遍历每个节点的入度和出度，如果找到一个符合条件的节点，由于题目保证只有一个法官，我们可以直接返回结果；如果不存在符合条件的点，则返回 -1。 class Solution { public int findJudge(int n, int[][] trust) { int[] inDegrees = new int[n + 1]; int[] outDegrees = new int[n + 1]; for (int[] edge : trust) { int x = edge[0], y = edge[1]; ++inDegrees[y]; ++outDegrees[x]; } for (int i = 1; i = m || j < 0 || j >= n || matrix[i][j] = 0) { int[] clone = dist.clone(); for (int[] flight : flights) { int from = flight[0]; int to = flight[1]; int price = flight[2]; // s->t = s->x + x->t dist[to] = Math.min(dist[to], clone[from] + price); } } return dist[dst] >= INF ? -1 : dist[dst]; } } 797，所有可能的路径题目：给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序） graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
题目：给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求： 路径途经的所有单元格都的值都是 0 。路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。畅通路径的长度 是该路径途经的单元格总数。 思路：广义优先遍历，每层步数+1。
题目：假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请计算出粉刷完所有房子最少的花费成本。 思路1：前缀和 class Solution { public int minCost(int[][] costs) { int n=costs.length; int ans[][]=new int[n+1][3]; for(int i=1;i |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |